Micron Document
<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>Strassen algorithm</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/Strassen_algorithm"> <link href="./mw/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Strassen_algorithm rootpage-Strassen_algorithm skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Strassen algorithm</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">
<style data-mw-deduplicate="TemplateStyles:r1236090951">
/* start https://en.wikipedia.org/ */


.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}


/* end https://en.wikipedia.org/ */
</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with the <a href="Sch%C3%B6nhage%E2%80%93Strassen_algorithm" title="Schönhage–Strassen algorithm">Schönhage–Strassen algorithm</a> for multiplication of polynomials.</div>
<p>In <a href="Linear_algebra" title="Linear algebra">linear algebra</a>, the <b>Strassen algorithm</b>, named after <a href="Volker_Strassen" title="Volker Strassen">Volker Strassen</a>, is an <a href="Matrix_multiplication_algorithm" title="Matrix multiplication algorithm">algorithm for matrix multiplication</a>. It is faster than the standard matrix multiplication algorithm for large matrices, with a better <a href="Asymptotic_complexity" class="mw-redirect" title="Asymptotic complexity">asymptotic complexity</a> (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{\log _{2}7})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>log</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⁡<!-- ⁡ --></mo>
<mn>7</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O(n^{\log _{2}7})}</annotation>
</semantics>
</math></span><img src="./1275da692ad0debb466d04d2a1cdd435e19a1fb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.352ex; height:3.176ex;" alt="{\displaystyle O(n^{\log _{2}7})}" loading="lazy"></span> versus <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{3})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O(n^{3})}</annotation>
</semantics>
</math></span><img src="./6b04f5c5cfea38f43406d9442387ad28555e2609.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{3})}" loading="lazy"></span>), although the naive algorithm is often better for smaller matrices. The Strassen algorithm is slower than <a href="Computational_complexity_of_matrix_multiplication" title="Computational complexity of matrix multiplication">the fastest known algorithms</a> for extremely large matrices, but such <a href="Galactic_algorithm" title="Galactic algorithm">galactic algorithms</a> are not useful in practice, as they are much slower for matrices of practical size. For small matrices even faster algorithms exist.
</p><p>Strassen's algorithm works for any <a href="Ring_(mathematics)" title="Ring (mathematics)">ring</a>, such as plus/multiply, but not all <a href="Semirings" class="mw-redirect" title="Semirings">semirings</a>, such as <a href="Min-plus_matrix_multiplication" title="Min-plus matrix multiplication">min-plus</a> or <a href="Boolean_algebra" title="Boolean algebra">boolean algebra</a>, where the naive algorithm still works, and so called combinatorial matrix multiplication.
</p>
<meta property="mw:PageProp/toc">
<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>
<p><a href="Volker_Strassen" title="Volker Strassen">Volker Strassen</a> first published this algorithm in 1969 and thereby proved that the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{3}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n^{3}}</annotation>
</semantics>
</math></span><img src="./3e9d1a52e455a7a5272a345b2697e35f1579b681.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.449ex; height:2.676ex;" alt="{\displaystyle n^{3}}" loading="lazy"></span> general matrix multiplication algorithm was not optimal.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The Strassen algorithm's publication resulted in more research about matrix multiplication that led to both asymptotically lower bounds and improved computational upper bounds.
</p>
<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

<p>Let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A}</annotation>
</semantics>
</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>B</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle B}</annotation>
</semantics>
</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> be two <a href="Square_matrix" title="Square matrix">square matrices</a> over a <a href="Ring_(mathematics)" title="Ring (mathematics)">ring</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {R}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">R</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {R}}}</annotation>
</semantics>
</math></span><img src="./74532dc308c806964b832df0d0d73352195c2f2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.971ex; height:2.176ex;" alt="{\displaystyle {\mathcal {R}}}" loading="lazy"></span>, for example matrices whose entries are integers or the real numbers. The goal of matrix multiplication is to calculate the matrix product <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C=AB}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>C</mi>
<mo>=</mo>
<mi>A</mi>
<mi>B</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C=AB}</annotation>
</semantics>
</math></span><img src="./636d3b809b596fe5cd46c13aff3deb285f18cba3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.372ex; height:2.176ex;" alt="{\displaystyle C=AB}" loading="lazy"></span>. The following exposition of the algorithm assumes that all of these matrices have sizes that are powers of two (i.e., <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A,\,B,\,C\in \operatorname {Matr} _{2^{n}\times 2^{n}}({\mathcal {R}})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
<mo>,</mo>
<mspace width="thinmathspace"></mspace>
<mi>B</mi>
<mo>,</mo>
<mspace width="thinmathspace"></mspace>
<mi>C</mi>
<mo>∈<!-- ∈ --></mo>
<msub>
<mi>Matr</mi>
<mrow class="MJX-TeXAtom-ORD">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
<mo>×<!-- × --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mrow>
</msub>
<mo>⁡<!-- ⁡ --></mo>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">R</mi>
</mrow>
</mrow>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A,\,B,\,C\in \operatorname {Matr} _{2^{n}\times 2^{n}}({\mathcal {R}})}</annotation>
</semantics>
</math></span><img src="./527d65a4d8ece14b50ebca478c486258515a7b42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.93ex; height:2.843ex;" alt="{\displaystyle A,\,B,\,C\in \operatorname {Matr} _{2^{n}\times 2^{n}}({\mathcal {R}})}" loading="lazy"></span>), but this is only conceptually necessary — if the matrices <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A}</annotation>
</semantics>
</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>B</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle B}</annotation>
</semantics>
</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> are not of type <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}\times 2^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
<mo>×<!-- × --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n}\times 2^{n}}</annotation>
</semantics>
</math></span><img src="./224a4a2c00116d57f7d93bd1116d1518837f1c28.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.602ex; height:2.343ex;" alt="{\displaystyle 2^{n}\times 2^{n}}" loading="lazy"></span>, the "missing" rows and columns can be filled with zeros to obtain matrices with sizes of powers of two — though real implementations of the algorithm do not do this in practice.
</p><p>The Strassen algorithm partitions <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A}</annotation>
</semantics>
</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>B</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle B}</annotation>
</semantics>
</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>C</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C}</annotation>
</semantics>
</math></span><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></span> into equally sized <a href="Block_matrix" title="Block matrix">block matrices</a>
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A={\begin{bmatrix}A_{11}&amp;A_{12}\\A_{21}&amp;A_{22}\end{bmatrix}},\quad B={\begin{bmatrix}B_{11}&amp;B_{12}\\B_{21}&amp;B_{22}\end{bmatrix}},\quad C={\begin{bmatrix}C_{11}&amp;C_{12}\\C_{21}&amp;C_{22}\end{bmatrix}},\quad }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
</mtd>
<mtd>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
</mtd>
<mtd>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>,</mo>
<mspace width="1em"></mspace>
<mi>B</mi>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
</mtd>
<mtd>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
</mtd>
<mtd>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>,</mo>
<mspace width="1em"></mspace>
<mi>C</mi>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
</mtd>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
</mtd>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>,</mo>
<mspace width="1em"></mspace>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A={\begin{bmatrix}A_{11}&amp;A_{12}\\A_{21}&amp;A_{22}\end{bmatrix}},\quad B={\begin{bmatrix}B_{11}&amp;B_{12}\\B_{21}&amp;B_{22}\end{bmatrix}},\quad C={\begin{bmatrix}C_{11}&amp;C_{12}\\C_{21}&amp;C_{22}\end{bmatrix}},\quad }</annotation>
</semantics>
</math></span><img src="./c998aa21de3dffad2a57b3fba64609a3b41775f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:62.434ex; height:6.176ex;" alt="{\displaystyle A={\begin{bmatrix}A_{11}&amp;A_{12}\\A_{21}&amp;A_{22}\end{bmatrix}},\quad B={\begin{bmatrix}B_{11}&amp;B_{12}\\B_{21}&amp;B_{22}\end{bmatrix}},\quad C={\begin{bmatrix}C_{11}&amp;C_{12}\\C_{21}&amp;C_{22}\end{bmatrix}},\quad }" loading="lazy"></span></dd></dl>
<p>with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mi>j</mi>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mi>j</mi>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mi>j</mi>
</mrow>
</msub>
<mo>∈<!-- ∈ --></mo>
<msub>
<mi>Mat</mi>
<mrow class="MJX-TeXAtom-ORD">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msup>
<mo>×<!-- × --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msup>
</mrow>
</msub>
<mo>⁡<!-- ⁡ --></mo>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">R</mi>
</mrow>
</mrow>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})}</annotation>
</semantics>
</math></span><img src="./8e3aa933724d0a491af9c0088ab81c1e7d567173.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:30.982ex; height:3.009ex;" alt="{\displaystyle A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})}" loading="lazy"></span>. The naive algorithm would be:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}C_{11}&amp;C_{12}\\C_{21}&amp;C_{22}\end{bmatrix}}={\begin{bmatrix}A_{11}{\color {red}\times }B_{11}+A_{12}{\color {red}\times }B_{21}\quad &amp;A_{11}{\color {red}\times }B_{12}+A_{12}{\color {red}\times }B_{22}\\A_{21}{\color {red}\times }B_{11}+A_{22}{\color {red}\times }B_{21}\quad &amp;A_{21}{\color {red}\times }B_{12}+A_{22}{\color {red}\times }B_{22}\end{bmatrix}}.}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
</mtd>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
</mtd>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mspace width="1em"></mspace>
</mtd>
<mtd>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mspace width="1em"></mspace>
</mtd>
<mtd>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>.</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}C_{11}&amp;C_{12}\\C_{21}&amp;C_{22}\end{bmatrix}}={\begin{bmatrix}A_{11}{\color {red}\times }B_{11}+A_{12}{\color {red}\times }B_{21}\quad &amp;A_{11}{\color {red}\times }B_{12}+A_{12}{\color {red}\times }B_{22}\\A_{21}{\color {red}\times }B_{11}+A_{22}{\color {red}\times }B_{21}\quad &amp;A_{21}{\color {red}\times }B_{12}+A_{22}{\color {red}\times }B_{22}\end{bmatrix}}.}</annotation>
</semantics>
</math></span><img src="./1a0987367a9e1da177649be14d1aa1f1cf2e6b54.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:66.154ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}C_{11}&amp;C_{12}\\C_{21}&amp;C_{22}\end{bmatrix}}={\begin{bmatrix}A_{11}{\color {red}\times }B_{11}+A_{12}{\color {red}\times }B_{21}\quad &amp;A_{11}{\color {red}\times }B_{12}+A_{12}{\color {red}\times }B_{22}\\A_{21}{\color {red}\times }B_{11}+A_{22}{\color {red}\times }B_{21}\quad &amp;A_{21}{\color {red}\times }B_{12}+A_{22}{\color {red}\times }B_{22}\end{bmatrix}}.}" loading="lazy"></span></dd></dl>
<p>This construction does not reduce the number of multiplications: 8 multiplications of matrix blocks are still needed to calculate the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{ij}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mi>j</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C_{ij}}</annotation>
</semantics>
</math></span><img src="./70b3f8ea18a9b9a0dbe09dae212a623820b217d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.139ex; height:2.843ex;" alt="{\displaystyle C_{ij}}" loading="lazy"></span> matrices, the same number of multiplications needed when using standard matrix multiplication.
</p><p>The Strassen algorithm defines instead new values:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}M_{1}&amp;=(A_{11}+A_{22}){\color {red}\times }(B_{11}+B_{22});\\M_{2}&amp;=(A_{21}+A_{22}){\color {red}\times }B_{11};\\M_{3}&amp;=A_{11}{\color {red}\times }(B_{12}-B_{22});\\M_{4}&amp;=A_{22}{\color {red}\times }(B_{21}-B_{11});\\M_{5}&amp;=(A_{11}+A_{12}){\color {red}\times }B_{22};\\M_{6}&amp;=(A_{21}-A_{11}){\color {red}\times }(B_{11}+B_{12});\\M_{7}&amp;=(A_{12}-A_{22}){\color {red}\times }(B_{21}+B_{22}),\\\end{aligned}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true">
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<mo stretchy="false">(</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<mo stretchy="false">(</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<mo stretchy="false">(</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>5</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>6</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<mo stretchy="false">(</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>7</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<mo stretchy="false">(</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>,</mo>
</mtd>
</mtr>
</mtable>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}M_{1}&amp;=(A_{11}+A_{22}){\color {red}\times }(B_{11}+B_{22});\\M_{2}&amp;=(A_{21}+A_{22}){\color {red}\times }B_{11};\\M_{3}&amp;=A_{11}{\color {red}\times }(B_{12}-B_{22});\\M_{4}&amp;=A_{22}{\color {red}\times }(B_{21}-B_{11});\\M_{5}&amp;=(A_{11}+A_{12}){\color {red}\times }B_{22};\\M_{6}&amp;=(A_{21}-A_{11}){\color {red}\times }(B_{11}+B_{12});\\M_{7}&amp;=(A_{12}-A_{22}){\color {red}\times }(B_{21}+B_{22}),\\\end{aligned}}}</annotation>
</semantics>
</math></span><img src="./27374610da00c63f3ba5924f3997248e054bd698.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -10.338ex; width:33.432ex; height:21.843ex;" alt="{\displaystyle {\begin{aligned}M_{1}&amp;=(A_{11}+A_{22}){\color {red}\times }(B_{11}+B_{22});\\M_{2}&amp;=(A_{21}+A_{22}){\color {red}\times }B_{11};\\M_{3}&amp;=A_{11}{\color {red}\times }(B_{12}-B_{22});\\M_{4}&amp;=A_{22}{\color {red}\times }(B_{21}-B_{11});\\M_{5}&amp;=(A_{11}+A_{12}){\color {red}\times }B_{22};\\M_{6}&amp;=(A_{21}-A_{11}){\color {red}\times }(B_{11}+B_{12});\\M_{7}&amp;=(A_{12}-A_{22}){\color {red}\times }(B_{21}+B_{22}),\\\end{aligned}}}" loading="lazy"></span></dd></dl>
<p>using only 7 multiplications (one for each <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{k}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle M_{k}}</annotation>
</semantics>
</math></span><img src="./43175c381ee6ba2694520af1f1a26c676a2726ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.343ex; height:2.509ex;" alt="{\displaystyle M_{k}}" loading="lazy"></span>) instead of 8. We may now express the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{ij}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mi>j</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C_{ij}}</annotation>
</semantics>
</math></span><img src="./70b3f8ea18a9b9a0dbe09dae212a623820b217d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.139ex; height:2.843ex;" alt="{\displaystyle C_{ij}}" loading="lazy"></span> in terms of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{k}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>k</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle M_{k}}</annotation>
</semantics>
</math></span><img src="./43175c381ee6ba2694520af1f1a26c676a2726ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.343ex; height:2.509ex;" alt="{\displaystyle M_{k}}" loading="lazy"></span>:
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}C_{11}&amp;C_{12}\\C_{21}&amp;C_{22}\end{bmatrix}}={\begin{bmatrix}M_{1}+M_{4}-M_{5}+M_{7}\quad &amp;M_{3}+M_{5}\\M_{2}+M_{4}\quad &amp;M_{1}-M_{2}+M_{3}+M_{6}\end{bmatrix}}.}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
</mtd>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
</mtd>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>5</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>7</mn>
</mrow>
</msub>
<mspace width="1em"></mspace>
</mtd>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>5</mn>
</mrow>
</msub>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
<mspace width="1em"></mspace>
</mtd>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>6</mn>
</mrow>
</msub>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>.</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}C_{11}&amp;C_{12}\\C_{21}&amp;C_{22}\end{bmatrix}}={\begin{bmatrix}M_{1}+M_{4}-M_{5}+M_{7}\quad &amp;M_{3}+M_{5}\\M_{2}+M_{4}\quad &amp;M_{1}-M_{2}+M_{3}+M_{6}\end{bmatrix}}.}</annotation>
</semantics>
</math></span><img src="./85d6d189229319e21cf67d1b18b7f8a71415f0d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:67.711ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}C_{11}&amp;C_{12}\\C_{21}&amp;C_{22}\end{bmatrix}}={\begin{bmatrix}M_{1}+M_{4}-M_{5}+M_{7}\quad &amp;M_{3}+M_{5}\\M_{2}+M_{4}\quad &amp;M_{1}-M_{2}+M_{3}+M_{6}\end{bmatrix}}.}" loading="lazy"></span></dd></dl>
<p>We recursively iterate this division process until the <a href="Submatrices" class="mw-redirect" title="Submatrices">submatrices</a> degenerate into numbers (elements of the ring <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {R}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">R</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {R}}}</annotation>
</semantics>
</math></span><img src="./74532dc308c806964b832df0d0d73352195c2f2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.971ex; height:2.176ex;" alt="{\displaystyle {\mathcal {R}}}" loading="lazy"></span>). If, as mentioned above, the original matrix had a size that was not a power of 2, then the resulting product will have zero rows and columns just like <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>A</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A}</annotation>
</semantics>
</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>B</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle B}</annotation>
</semantics>
</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span>, and these will then be stripped at this point to obtain the (smaller) matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>C</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C}</annotation>
</semantics>
</math></span><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></span> we really wanted.
</p><p>Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> However, it has been observed that this crossover point has been increasing in recent years, and a 2010 study found that even a single step of Strassen's algorithm is often not beneficial on current architectures, compared to a highly optimized traditional multiplication, until matrix sizes exceed 1000 or more, and even for matrix sizes of several thousand the benefit is typically marginal at best (around 10% or less).<sup id="cite_ref-dalberto_3-0" class="reference"><a href="#cite_note-dalberto-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> A more recent study (2016) observed benefits for matrices as small as 512 and a benefit around 20%.<sup id="cite_ref-huang_et_al._4-0" class="reference"><a href="#cite_note-huang_et_al.-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="Improvements_to_Strassen_algorithm">Improvements to Strassen algorithm</h2></div>
<div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Matrix_multiplication_algorithm#Sub-cubic_algorithms" title="Matrix multiplication algorithm">Matrix multiplication algorithm §&nbsp;Sub-cubic algorithms</a>, and <a href="Computational_complexity_of_matrix_multiplication" title="Computational complexity of matrix multiplication">Computational complexity of matrix multiplication</a></div>
<p>It is possible to reduce the number of matrix additions by instead using the following form discovered by Winograd in 1971:<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>
</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}a&amp;b\\c&amp;d\end{bmatrix}}{\begin{bmatrix}A&amp;C\\B&amp;D\end{bmatrix}}={\begin{bmatrix}t+b{\color {red}\times }B&amp;w+v+(a+b-c-d){\color {red}\times }D\\w+u+d{\color {red}\times }(B+C-A-D)&amp;w+u+v\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mi>a</mi>
</mtd>
<mtd>
<mi>b</mi>
</mtd>
</mtr>
<mtr>
<mtd>
<mi>c</mi>
</mtd>
<mtd>
<mi>d</mi>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mi>A</mi>
</mtd>
<mtd>
<mi>C</mi>
</mtd>
</mtr>
<mtr>
<mtd>
<mi>B</mi>
</mtd>
<mtd>
<mi>D</mi>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mi>t</mi>
<mo>+</mo>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<mi>B</mi>
</mtd>
<mtd>
<mi>w</mi>
<mo>+</mo>
<mi>v</mi>
<mo>+</mo>
<mo stretchy="false">(</mo>
<mi>a</mi>
<mo>+</mo>
<mi>b</mi>
<mo>−<!-- − --></mo>
<mi>c</mi>
<mo>−<!-- − --></mo>
<mi>d</mi>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<mi>D</mi>
</mtd>
</mtr>
<mtr>
<mtd>
<mi>w</mi>
<mo>+</mo>
<mi>u</mi>
<mo>+</mo>
<mi>d</mi>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<mo stretchy="false">(</mo>
<mi>B</mi>
<mo>+</mo>
<mi>C</mi>
<mo>−<!-- − --></mo>
<mi>A</mi>
<mo>−<!-- − --></mo>
<mi>D</mi>
<mo stretchy="false">)</mo>
</mtd>
<mtd>
<mi>w</mi>
<mo>+</mo>
<mi>u</mi>
<mo>+</mo>
<mi>v</mi>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}a&amp;b\\c&amp;d\end{bmatrix}}{\begin{bmatrix}A&amp;C\\B&amp;D\end{bmatrix}}={\begin{bmatrix}t+b{\color {red}\times }B&amp;w+v+(a+b-c-d){\color {red}\times }D\\w+u+d{\color {red}\times }(B+C-A-D)&amp;w+u+v\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./c97986ea249ab4638b50e8ffed515a2e3e011fea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:82.032ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}a&amp;b\\c&amp;d\end{bmatrix}}{\begin{bmatrix}A&amp;C\\B&amp;D\end{bmatrix}}={\begin{bmatrix}t+b{\color {red}\times }B&amp;w+v+(a+b-c-d){\color {red}\times }D\\w+u+d{\color {red}\times }(B+C-A-D)&amp;w+u+v\end{bmatrix}}}" loading="lazy"></span>
</p><p>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=a{\color {red}\times }A,\;u=(c-a){\color {red}\times }(C-D),\;v=(c+d){\color {red}\times }(C-A),\;w=t+(c+d-a){\color {red}\times }(A+D-C)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>t</mi>
<mo>=</mo>
<mi>a</mi>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<mi>A</mi>
<mo>,</mo>
<mspace width="thickmathspace"></mspace>
<mi>u</mi>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mi>c</mi>
<mo>−<!-- − --></mo>
<mi>a</mi>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<mo stretchy="false">(</mo>
<mi>C</mi>
<mo>−<!-- − --></mo>
<mi>D</mi>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mspace width="thickmathspace"></mspace>
<mi>v</mi>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mi>c</mi>
<mo>+</mo>
<mi>d</mi>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<mo stretchy="false">(</mo>
<mi>C</mi>
<mo>−<!-- − --></mo>
<mi>A</mi>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mspace width="thickmathspace"></mspace>
<mi>w</mi>
<mo>=</mo>
<mi>t</mi>
<mo>+</mo>
<mo stretchy="false">(</mo>
<mi>c</mi>
<mo>+</mo>
<mi>d</mi>
<mo>−<!-- − --></mo>
<mi>a</mi>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<mo stretchy="false">(</mo>
<mi>A</mi>
<mo>+</mo>
<mi>D</mi>
<mo>−<!-- − --></mo>
<mi>C</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle t=a{\color {red}\times }A,\;u=(c-a){\color {red}\times }(C-D),\;v=(c+d){\color {red}\times }(C-A),\;w=t+(c+d-a){\color {red}\times }(A+D-C)}</annotation>
</semantics>
</math></span><img src="./928e4df140142c7d2d281b6e45185915a94e2ae8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:90.402ex; height:2.843ex;" alt="{\displaystyle t=a{\color {red}\times }A,\;u=(c-a){\color {red}\times }(C-D),\;v=(c+d){\color {red}\times }(C-A),\;w=t+(c+d-a){\color {red}\times }(A+D-C)}" loading="lazy"></span>.
</p><p>This reduces the number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same.<sup id="cite_ref-FOOTNOTEKnuth1997500_6-0" class="reference"><a href="#cite_note-FOOTNOTEKnuth1997500-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>
</p><p>The algorithm was further optimised in 2017 using an alternative basis,<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> reducing the number of matrix additions per bilinear step to 12 while maintaining the number of matrix multiplications, and again in 2023:<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>
</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}A_{22}&amp;=A_{12}-A_{21}+A_{22};\\B_{22}&amp;=B_{12}-B_{21}+B_{22},\end{aligned}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true">
<mtr>
<mtd>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo>,</mo>
</mtd>
</mtr>
</mtable>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}A_{22}&amp;=A_{12}-A_{21}+A_{22};\\B_{22}&amp;=B_{12}-B_{21}+B_{22},\end{aligned}}}</annotation>
</semantics>
</math></span><img src="./ea2c34225ef9b99d510eca38d480210b3897f441.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:24.738ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}A_{22}&amp;=A_{12}-A_{21}+A_{22};\\B_{22}&amp;=B_{12}-B_{21}+B_{22},\end{aligned}}}" loading="lazy"></span>
</p>
<style data-mw-deduplicate="TemplateStyles:r1216972533">
/* start https://en.wikipedia.org/ */


.mw-parser-output .col-begin{border-collapse:collapse;padding:0;color:inherit;width:100%;border:0;margin:0}.mw-parser-output .col-begin-small{font-size:90%}.mw-parser-output .col-break{vertical-align:top;text-align:left}.mw-parser-output .col-break-2{width:50%}.mw-parser-output .col-break-3{width:33.3%}.mw-parser-output .col-break-4{width:25%}.mw-parser-output .col-break-5{width:20%}@media(max-width:720px){.mw-parser-output .col-begin,.mw-parser-output .col-begin>tbody,.mw-parser-output .col-begin>tbody>tr,.mw-parser-output .col-begin>tbody>tr>td{display:block!important;width:100%!important}.mw-parser-output .col-break{padding-left:0!important}}


/* end https://en.wikipedia.org/ */
</style><div>
<table class="col-begin" role="presentation">


<tbody><tr>
<td class="col-break">
<p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}t_{1}&amp;=A_{21}+A_{22};\\t_{2}&amp;=A_{22}-A_{12};\\t_{3}&amp;=A_{22}-A_{11};\\t_{4}&amp;=B_{22}-B_{11};\\t_{5}&amp;=B_{21}+B_{22};\\t_{6}&amp;=B_{22}-B_{12},\end{aligned}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true">
<mtr>
<mtd>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>5</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>6</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mo>,</mo>
</mtd>
</mtr>
</mtable>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}t_{1}&amp;=A_{21}+A_{22};\\t_{2}&amp;=A_{22}-A_{12};\\t_{3}&amp;=A_{22}-A_{11};\\t_{4}&amp;=B_{22}-B_{11};\\t_{5}&amp;=B_{21}+B_{22};\\t_{6}&amp;=B_{22}-B_{12},\end{aligned}}}</annotation>
</semantics>
</math></span><img src="./2a9fd9c3492a1030296f341de4ebca6fa9f651ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.338ex; width:16.511ex; height:17.843ex;" alt="{\displaystyle {\begin{aligned}t_{1}&amp;=A_{21}+A_{22};\\t_{2}&amp;=A_{22}-A_{12};\\t_{3}&amp;=A_{22}-A_{11};\\t_{4}&amp;=B_{22}-B_{11};\\t_{5}&amp;=B_{21}+B_{22};\\t_{6}&amp;=B_{22}-B_{12},\end{aligned}}}" loading="lazy"></span>
</p>
</td>
<td class="col-break">
<p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}M_{1}&amp;=A_{11}{\color {red}\times }B_{11};\\M_{2}&amp;=A_{12}{\color {red}\times }B_{21};\\M_{3}&amp;=A_{21}{\color {red}\times }t_{4};\\M_{4}&amp;=A_{22}{\color {red}\times }B_{22};\\M_{5}&amp;=t_{1}{\color {red}\times }t_{5};\\M_{6}&amp;=t_{2}{\color {red}\times }t_{6};\\M_{7}&amp;=t_{3}{\color {red}\times }B_{12},\end{aligned}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true">
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>5</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>5</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>6</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>6</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>7</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>t</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mstyle mathcolor="red">
<mo>×<!-- × --></mo>
</mstyle>
</mrow>
<msub>
<mi>B</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mo>,</mo>
</mtd>
</mtr>
</mtable>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}M_{1}&amp;=A_{11}{\color {red}\times }B_{11};\\M_{2}&amp;=A_{12}{\color {red}\times }B_{21};\\M_{3}&amp;=A_{21}{\color {red}\times }t_{4};\\M_{4}&amp;=A_{22}{\color {red}\times }B_{22};\\M_{5}&amp;=t_{1}{\color {red}\times }t_{5};\\M_{6}&amp;=t_{2}{\color {red}\times }t_{6};\\M_{7}&amp;=t_{3}{\color {red}\times }B_{12},\end{aligned}}}</annotation>
</semantics>
</math></span><img src="./cd30a737d00240c493d1e96766f06f46ab8ba2b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -9.838ex; width:16.873ex; height:20.843ex;" alt="{\displaystyle {\begin{aligned}M_{1}&amp;=A_{11}{\color {red}\times }B_{11};\\M_{2}&amp;=A_{12}{\color {red}\times }B_{21};\\M_{3}&amp;=A_{21}{\color {red}\times }t_{4};\\M_{4}&amp;=A_{22}{\color {red}\times }B_{22};\\M_{5}&amp;=t_{1}{\color {red}\times }t_{5};\\M_{6}&amp;=t_{2}{\color {red}\times }t_{6};\\M_{7}&amp;=t_{3}{\color {red}\times }B_{12},\end{aligned}}}" loading="lazy"></span>
</p>
</td>
<td class="col-break">
<p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}C_{11}&amp;=M_{1}+M_{2};\\C_{12}&amp;=M_{5}-M_{7};\\C_{21}&amp;=M_{3}+M_{6};\\C_{22}&amp;=M_{5}+M_{6}-M_{2}-M_{4}.\\\end{aligned}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true">
<mtr>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>11</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>5</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>7</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>6</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>5</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>6</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
<mo>.</mo>
</mtd>
</mtr>
</mtable>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}C_{11}&amp;=M_{1}+M_{2};\\C_{12}&amp;=M_{5}-M_{7};\\C_{21}&amp;=M_{3}+M_{6};\\C_{22}&amp;=M_{5}+M_{6}-M_{2}-M_{4}.\\\end{aligned}}}</annotation>
</semantics>
</math></span><img src="./a104e99ea3f6feca04b14f1da22fbb689093ff7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.338ex; width:29.789ex; height:11.843ex;" alt="{\displaystyle {\begin{aligned}C_{11}&amp;=M_{1}+M_{2};\\C_{12}&amp;=M_{5}-M_{7};\\C_{21}&amp;=M_{3}+M_{6};\\C_{22}&amp;=M_{5}+M_{6}-M_{2}-M_{4}.\\\end{aligned}}}" loading="lazy"></span>
</p>
</td></tr></tbody></table></div>
<p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}C_{12}&amp;=C_{12}-C_{22};\\C_{21}&amp;=C_{22}-C_{21},\end{aligned}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true">
<mtr>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>12</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo>;</mo>
</mtd>
</mtr>
<mtr>
<mtd>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
</mtd>
<mtd>
<mi></mi>
<mo>=</mo>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
<mo>−<!-- − --></mo>
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mo>,</mo>
</mtd>
</mtr>
</mtable>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}C_{12}&amp;=C_{12}-C_{22};\\C_{21}&amp;=C_{22}-C_{21},\end{aligned}}}</annotation>
</semantics>
</math></span><img src="./747f27d9612d34a29189f546d7ce9caa08817cb7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:17.951ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}C_{12}&amp;=C_{12}-C_{22};\\C_{21}&amp;=C_{22}-C_{21},\end{aligned}}}" loading="lazy"></span>
</p>
<div class="mw-heading mw-heading2"><h2 id="Asymptotic_complexity">Asymptotic complexity</h2></div>
<p>The outline of the algorithm above showed that one can get away with just 7, instead of the traditional 8, matrix-matrix multiplications for the sub-blocks of the matrix. On the other hand, one has to do additions and subtractions of blocks, though this is of no concern for the overall complexity: Adding matrices of size <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N/2}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N/2}</annotation>
</semantics>
</math></span><img src="./45c51c21b2bc7ea5e2fcae8f0f4aa49f6f19ebaf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.389ex; height:2.843ex;" alt="{\displaystyle N/2}" loading="lazy"></span> requires only <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N/2)^{2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<mi>N</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
<msup>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle (N/2)^{2}}</annotation>
</semantics>
</math></span><img src="./a1ce48a9d5fce0193a462f4e0d14795c07c893e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.252ex; height:3.176ex;" alt="{\displaystyle (N/2)^{2}}" loading="lazy"></span> operations whereas multiplication is substantially more expensive (traditionally <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2(N/2)^{3}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>2</mn>
<mo stretchy="false">(</mo>
<mi>N</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
<msup>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2(N/2)^{3}}</annotation>
</semantics>
</math></span><img src="./7b75251c0de3e79df6ab0b9ddc25bffe83f2b381.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.415ex; height:3.176ex;" alt="{\displaystyle 2(N/2)^{3}}" loading="lazy"></span> addition or multiplication operations).
</p><p>The question then is how many operations exactly one needs for Strassen's algorithms, and how this compares with the standard matrix multiplication that takes approximately <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2N^{3}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>2</mn>
<msup>
<mi>N</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2N^{3}}</annotation>
</semantics>
</math></span><img src="./503fc059c7391ff474880c367514709769e347fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.34ex; height:2.676ex;" alt="{\displaystyle 2N^{3}}" loading="lazy"></span> (where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=2^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
<mo>=</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N=2^{n}}</annotation>
</semantics>
</math></span><img src="./d47454e9a8a33d7f62a8b689ecda44afd41e51be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.543ex; height:2.343ex;" alt="{\displaystyle N=2^{n}}" loading="lazy"></span>) arithmetic operations, i.e. an asymptotic complexity <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (N^{3})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi mathvariant="normal">Θ<!-- Θ --></mi>
<mo stretchy="false">(</mo>
<msup>
<mi>N</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \Theta (N^{3})}</annotation>
</semantics>
</math></span><img src="./0e90b1a932696975b88dda14997851836cf9724a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.795ex; height:3.176ex;" alt="{\displaystyle \Theta (N^{3})}" loading="lazy"></span>.
</p><p>The number of additions and multiplications required in the Strassen algorithm can be calculated as follows: let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f(n)}</annotation>
</semantics>
</math></span><img src="./c1c49fad1eccc4e9af1e4f23f32efdc3ac4da973.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.483ex; height:2.843ex;" alt="{\displaystyle f(n)}" loading="lazy"></span> be the number of operations for a <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}\times 2^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
<mo>×<!-- × --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n}\times 2^{n}}</annotation>
</semantics>
</math></span><img src="./224a4a2c00116d57f7d93bd1116d1518837f1c28.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.602ex; height:2.343ex;" alt="{\displaystyle 2^{n}\times 2^{n}}" loading="lazy"></span> matrix. Then by recursive application of the Strassen algorithm, we see that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)=7f(n-1)+l4^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mn>7</mn>
<mi>f</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>l</mi>
<msup>
<mn>4</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f(n)=7f(n-1)+l4^{n}}</annotation>
</semantics>
</math></span><img src="./1289b383d9e62564d78317ab133880143e94ee2b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.144ex; height:2.843ex;" alt="{\displaystyle f(n)=7f(n-1)+l4^{n}}" loading="lazy"></span>, for some constant <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>l</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle l}</annotation>
</semantics>
</math></span><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"></span> that depends on the number of additions performed at each application of the algorithm. Hence <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(n)=(7+o(1))^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>f</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mn>7</mn>
<mo>+</mo>
<mi>o</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<msup>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f(n)=(7+o(1))^{n}}</annotation>
</semantics>
</math></span><img src="./1826f9f094ffd54dbfc53a216148dad11890515d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.711ex; height:2.843ex;" alt="{\displaystyle f(n)=(7+o(1))^{n}}" loading="lazy"></span>, i.e., the asymptotic complexity for multiplying matrices of size <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=2^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
<mo>=</mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N=2^{n}}</annotation>
</semantics>
</math></span><img src="./d47454e9a8a33d7f62a8b689ecda44afd41e51be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.543ex; height:2.343ex;" alt="{\displaystyle N=2^{n}}" loading="lazy"></span> using the Strassen algorithm is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.8074})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<mo stretchy="false">[</mo>
<mn>7</mn>
<mo>+</mo>
<mi>o</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<msup>
<mo stretchy="false">]</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>N</mi>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>log</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⁡<!-- ⁡ --></mo>
<mn>7</mn>
<mo>+</mo>
<mi>o</mi>
<mo stretchy="false">(</mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
</mrow>
</msup>
<mo stretchy="false">)</mo>
<mo>≈<!-- ≈ --></mo>
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>N</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2.8074</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.8074})}</annotation>
</semantics>
</math></span><img src="./511e64be8e75258905f4b3c61d73de72080e643c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.156ex; height:3.343ex;" alt="{\displaystyle O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.8074})}" loading="lazy"></span>. The reduction in the number of arithmetic operations however comes at the price of a somewhat reduced <a href="Numerical_stability" title="Numerical stability">numerical stability</a>,<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> and the algorithm also requires significantly more memory compared to the naive algorithm. Both initial matrices must have their dimensions expanded to the next power of 2, which results in storing up to four times as many elements, and the seven auxiliary matrices each contain a quarter of the elements in the expanded ones.
</p><p>Strassen's algorithm needs to be compared to the "naive" way of doing the matrix multiplication that would require 8 instead of 7 multiplications of sub-blocks. This would then give rise to the complexity one expects from the standard approach: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(8^{n})=O(N^{\log _{2}8})=O(N^{3})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mn>8</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>N</mi>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>log</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⁡<!-- ⁡ --></mo>
<mn>8</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>N</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O(8^{n})=O(N^{\log _{2}8})=O(N^{3})}</annotation>
</semantics>
</math></span><img src="./1a2bea092225ca588928d2a7e78677e9224828c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29ex; height:3.176ex;" alt="{\displaystyle O(8^{n})=O(N^{\log _{2}8})=O(N^{3})}" loading="lazy"></span>. The comparison of these two algorithms shows that <i>asymptotically</i>, Strassen's algorithm is faster: There exists a size <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{\text{threshold}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>N</mi>
<mrow class="MJX-TeXAtom-ORD">
<mtext>threshold</mtext>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N_{\text{threshold}}}</annotation>
</semantics>
</math></span><img src="./34ff72c46167cc3ce8276d10d605412ce292f289.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.782ex; height:2.509ex;" alt="{\displaystyle N_{\text{threshold}}}" loading="lazy"></span> so that matrices that are larger are more efficiently multiplied with Strassen's algorithm than the "traditional" way. However, the asymptotic statement does not imply that Strassen's algorithm is <i>always</i> faster even for small matrices, and in practice this is in fact not the case: For small matrices, the cost of the additional additions of matrix blocks outweighs the savings in the number of multiplications. There are also other factors not captured by the analysis above, such as the difference in cost on today's hardware between loading data from memory onto processors vs. the cost of actually doing operations on this data. As a consequence of these sorts of considerations, Strassen's algorithm is typically only used on "large" matrices. This kind of effect is even more pronounced with alternative algorithms such as the one by <a href="Coppersmith-Winograd_algorithm" class="mw-redirect" title="Coppersmith-Winograd algorithm">Coppersmith and Winograd</a>: While <i>asymptotically</i> even faster, the cross-over point <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{\text{threshold}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>N</mi>
<mrow class="MJX-TeXAtom-ORD">
<mtext>threshold</mtext>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N_{\text{threshold}}}</annotation>
</semantics>
</math></span><img src="./34ff72c46167cc3ce8276d10d605412ce292f289.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.782ex; height:2.509ex;" alt="{\displaystyle N_{\text{threshold}}}" loading="lazy"></span> is so large that the algorithm is not generally used on matrices one encounters in practice.
</p>
<div class="mw-heading mw-heading3"><h3 id="Rank_or_bilinear_complexity">Rank or bilinear complexity</h3></div>
<p>The bilinear complexity or <b>rank</b> of a <a href="Bilinear_map" title="Bilinear map">bilinear map</a> is an important concept in the asymptotic complexity of matrix multiplication. The rank of a bilinear map <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \phi :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>ϕ<!-- ϕ --></mi>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">A</mi>
</mrow>
<mo>×<!-- × --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">B</mi>
</mrow>
<mo stretchy="false">→<!-- → --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">C</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \phi :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C} }</annotation>
</semantics>
</math></span><img src="./33d24ef25ea7374ef9e7c45f9014c6d34cb48fde.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.629ex; height:2.509ex;" alt="{\displaystyle \phi :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C} }" loading="lazy"></span> over a field <b>F</b> is defined as (somewhat of an <a href="Abuse_of_notation" title="Abuse of notation">abuse of notation</a>)
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(\phi /\mathbf {F} )=\min \left\{r\left|\exists f_{i}\in \mathbf {A} ^{*},g_{i}\in \mathbf {B} ^{*},w_{i}\in \mathbf {C} ,\forall \mathbf {a} \in \mathbf {A} ,\mathbf {b} \in \mathbf {B} ,\phi (\mathbf {a} ,\mathbf {b} )=\sum _{i=1}^{r}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}\right.\right\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>R</mi>
<mo stretchy="false">(</mo>
<mi>ϕ<!-- ϕ --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">F</mi>
</mrow>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mo movablelimits="true" form="prefix">min</mo>
<mrow>
<mo>{</mo>
<mrow>
<mi>r</mi>
<mrow>
<mo>|</mo>
<mrow>
<mi mathvariant="normal">∃<!-- ∃ --></mi>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>∈<!-- ∈ --></mo>
<msup>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">A</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo>∗<!-- ∗ --></mo>
</mrow>
</msup>
<mo>,</mo>
<msub>
<mi>g</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>∈<!-- ∈ --></mo>
<msup>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">B</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo>∗<!-- ∗ --></mo>
</mrow>
</msup>
<mo>,</mo>
<msub>
<mi>w</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo>∈<!-- ∈ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">C</mi>
</mrow>
<mo>,</mo>
<mi mathvariant="normal">∀<!-- ∀ --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
<mo>∈<!-- ∈ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">A</mi>
</mrow>
<mo>,</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
<mo>∈<!-- ∈ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">B</mi>
</mrow>
<mo>,</mo>
<mi>ϕ<!-- ϕ --></mi>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
<mo>,</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
<mo stretchy="false">)</mo>
<mo>=</mo>
<munderover>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>r</mi>
</mrow>
</munderover>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
<mo stretchy="false">)</mo>
<msub>
<mi>g</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
<mo stretchy="false">)</mo>
<msub>
<mi>w</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mrow>
<mo fence="true" stretchy="true" symmetric="true"></mo>
</mrow>
</mrow>
<mo>}</mo>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R(\phi /\mathbf {F} )=\min \left\{r\left|\exists f_{i}\in \mathbf {A} ^{*},g_{i}\in \mathbf {B} ^{*},w_{i}\in \mathbf {C} ,\forall \mathbf {a} \in \mathbf {A} ,\mathbf {b} \in \mathbf {B} ,\phi (\mathbf {a} ,\mathbf {b} )=\sum _{i=1}^{r}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}\right.\right\}}</annotation>
</semantics>
</math></span><img src="./b9f4866f89e5649f238a13b187fd7df51c548fc3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:90.497ex; height:7.509ex;" alt="{\displaystyle R(\phi /\mathbf {F} )=\min \left\{r\left|\exists f_{i}\in \mathbf {A} ^{*},g_{i}\in \mathbf {B} ^{*},w_{i}\in \mathbf {C} ,\forall \mathbf {a} \in \mathbf {A} ,\mathbf {b} \in \mathbf {B} ,\phi (\mathbf {a} ,\mathbf {b} )=\sum _{i=1}^{r}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}\right.\right\}}" loading="lazy"></span></dd></dl>
<p>In other words, the rank of a bilinear map is the length of its shortest bilinear computation.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> The existence of Strassen's algorithm shows that the rank of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\times 2}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>2</mn>
<mo>×<!-- × --></mo>
<mn>2</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2\times 2}</annotation>
</semantics>
</math></span><img src="./f8a0e3400ffb97d67c00267ed50cddfe824cbe80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.165ex; height:2.176ex;" alt="{\displaystyle 2\times 2}" loading="lazy"></span> matrix multiplication is no more than seven. To see this, let us express this algorithm (alongside the standard algorithm) as such a bilinear computation. In the case of matrices, the <a href="Dual_space" title="Dual space">dual spaces</a> <b>A</b>* and <b>B</b>* consist of maps into the field <b>F</b> induced by a scalar <b><a href="Dyadics#Product_of_dyadic_and_dyadic" title="Dyadics">double-dot product</a></b>, (i.e. in this case the sum of all the entries of a <a href="Hadamard_product_(matrices)" title="Hadamard product (matrices)">Hadamard product</a>.)
</p>
<table class="wikitable">
<tbody><tr>
<td></td>
<td colspan="3">Standard algorithm</td>
<td></td>
<td colspan="3">Strassen algorithm
</td></tr>
<tr>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>i</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle i}</annotation>
</semantics>
</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span></td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{i}(\mathbf {a} )}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f_{i}(\mathbf {a} )}</annotation>
</semantics>
</math></span><img src="./63e31a803b8e0fa808d81bfa97d9ae30230ae041.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.048ex; height:2.843ex;" alt="{\displaystyle f_{i}(\mathbf {a} )}" loading="lazy"></span></td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}(\mathbf {b} )}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>g</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle g_{i}(\mathbf {b} )}</annotation>
</semantics>
</math></span><img src="./867e53582a0fb7be4421d8038d5d88958e2576a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.203ex; height:2.843ex;" alt="{\displaystyle g_{i}(\mathbf {b} )}" loading="lazy"></span></td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>w</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle w_{i}}</annotation>
</semantics>
</math></span><img src="./fe22f0329d3ecb2e1880d44d191aba0e5475db68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.464ex; height:2.009ex;" alt="{\displaystyle w_{i}}" loading="lazy"></span></td>
<td></td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{i}(\mathbf {a} )}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle f_{i}(\mathbf {a} )}</annotation>
</semantics>
</math></span><img src="./63e31a803b8e0fa808d81bfa97d9ae30230ae041.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.048ex; height:2.843ex;" alt="{\displaystyle f_{i}(\mathbf {a} )}" loading="lazy"></span></td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}(\mathbf {b} )}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>g</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle g_{i}(\mathbf {b} )}</annotation>
</semantics>
</math></span><img src="./867e53582a0fb7be4421d8038d5d88958e2576a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.203ex; height:2.843ex;" alt="{\displaystyle g_{i}(\mathbf {b} )}" loading="lazy"></span></td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>w</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle w_{i}}</annotation>
</semantics>
</math></span><img src="./fe22f0329d3ecb2e1880d44d191aba0e5475db68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.464ex; height:2.009ex;" alt="{\displaystyle w_{i}}" loading="lazy"></span>
</td></tr>
<tr>
<td>1
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./23bc392d34269166fd50bbafc23a198b121fe56a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.091ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./86f76286037ce2f86c5dd8ef86ce95eaed25277b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.276ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./b55bcb3cd9a9d9eb3a8698103a479f5fad7a1ab5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}}" loading="lazy"></span>
</td>
<td>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./bd537f31776e1779bfe4d94fc26f6b139f4122b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.091ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./3f37bfe8766fc491b0fb06179997c89a959b61ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.276ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;1\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;1\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./d0df1bbd611c3587f00ad4c03a383bdd4ee469fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;1\end{bmatrix}}}" loading="lazy"></span>
</td></tr>
<tr>
<td>2
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./d9863ce0bd34446eceb0385628fbcbbfd40e84de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.091ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./1fd40636e1e6d5c3d20b6b506f27558160b64b23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.276ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./b55bcb3cd9a9d9eb3a8698103a479f5fad7a1ab5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}}" loading="lazy"></span>
</td>
<td>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;1\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;1\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./e470a066cd428833cb7eb15bcb6ea5ea2eb1b427.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.091ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;1\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./86f76286037ce2f86c5dd8ef86ce95eaed25277b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.276ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;-1\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;-1\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./fd0273cc98ee22787b92dfdf4610d1114cf53c7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:9.662ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;-1\end{bmatrix}}}" loading="lazy"></span>
</td></tr>
<tr>
<td>3
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./23bc392d34269166fd50bbafc23a198b121fe56a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.091ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./24fb9572bfd082ec62ca8756bab697c6e80c1cf5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.276ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./eb69343e096235ec162a5f08f9a59c684687c041.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}}" loading="lazy"></span>
</td>
<td>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./23bc392d34269166fd50bbafc23a198b121fe56a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.091ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;-1\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;-1\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./8236b40347be796ec6cc154667871a2daba90774.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:13.085ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;-1\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;1\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;1\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./cc596fbfe53bf6c9b65fb041eaadcc2ace0427be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;1\end{bmatrix}}}" loading="lazy"></span>
</td></tr>
<tr>
<td>4
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./d9863ce0bd34446eceb0385628fbcbbfd40e84de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.091ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./6303583e51c140b73cb5876c0995902c72d2beef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.276ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./eb69343e096235ec162a5f08f9a59c684687c041.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}}" loading="lazy"></span>
</td>
<td>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./f089c8be5c214a8677eb00ab390bafeb849d3159.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.091ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}-1&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}-1&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./f84010f25f988634dc1799edb73419340d56414b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:13.085ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}-1&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;0\\1&amp;0\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;0\\1&amp;0\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./8a8d2b9f853e837655faf65d3b0d1cde409759ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;0\\1&amp;0\end{bmatrix}}}" loading="lazy"></span>
</td></tr>
<tr>
<td>5
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./02d4d4c33021702764e9bd8304bdac5a36bfcfba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.091ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./86f76286037ce2f86c5dd8ef86ce95eaed25277b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.276ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./be2941cf378161813a34da344666cfa0eaaca54b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}}" loading="lazy"></span>
</td>
<td>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./defc91d9155a0c390880bcca6e04f972f7dc6226.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.091ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./6303583e51c140b73cb5876c0995902c72d2beef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.276ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}-1&amp;1\\0&amp;0\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}-1&amp;1\\0&amp;0\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./5c1608454bdf0a181c35f94fd71d15a27331491c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:9.662ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}-1&amp;1\\0&amp;0\end{bmatrix}}}" loading="lazy"></span>
</td></tr>
<tr>
<td>6
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./f089c8be5c214a8677eb00ab390bafeb849d3159.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.091ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./1fd40636e1e6d5c3d20b6b506f27558160b64b23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.276ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./be2941cf378161813a34da344666cfa0eaaca54b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}}" loading="lazy"></span>
</td>
<td>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}-1&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}-1&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./a2d15f906781b70d4beda49345dd5630150e7d1c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:12.899ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}-1&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./2db86c3c9838dab5c294cfcfd7535be0e3efa3ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.276ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./0f221644aba733e5b970c70ea85689320a2a73a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}}" loading="lazy"></span>
</td></tr>
<tr>
<td>7
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./02d4d4c33021702764e9bd8304bdac5a36bfcfba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.091ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;0\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./24fb9572bfd082ec62ca8756bab697c6e80c1cf5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.276ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;0\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./0f221644aba733e5b970c70ea85689320a2a73a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}}" loading="lazy"></span>
</td>
<td>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;-1\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;-1\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./ddee0bd92a833f2f1462c7249651cecb5ce7828b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:12.899ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;1\\0&amp;-1\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;1\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;1\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./b9d499a8d04a3b132e9840259645b23bdfec5871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.276ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\1&amp;1\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>1</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./b55bcb3cd9a9d9eb3a8698103a479f5fad7a1ab5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}1&amp;0\\0&amp;0\end{bmatrix}}}" loading="lazy"></span>
</td></tr>
<tr>
<td>8
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {a} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {a} }</annotation>
</semantics>
</math></span><img src="./f089c8be5c214a8677eb00ab390bafeb849d3159.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.091ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {a} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {b} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
<mo>:</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {b} }</annotation>
</semantics>
</math></span><img src="./6303583e51c140b73cb5876c0995902c72d2beef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:11.276ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}:\mathbf {b} }" loading="lazy"></span>
</td>
<td><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow>
<mo>[</mo>
<mtable rowspacing="4pt" columnspacing="1em">
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>0</mn>
</mtd>
</mtr>
<mtr>
<mtd>
<mn>0</mn>
</mtd>
<mtd>
<mn>1</mn>
</mtd>
</mtr>
</mtable>
<mo>]</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}}</annotation>
</semantics>
</math></span><img src="./0f221644aba733e5b970c70ea85689320a2a73a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:7.854ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}0&amp;0\\0&amp;1\end{bmatrix}}}" loading="lazy"></span>
</td>
<td>
</td>
<td colspan="3">
</td></tr>
<tr>
<td>
</td>
<td colspan="3"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{8}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
<mo>=</mo>
<munderover>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>8</mn>
</mrow>
</munderover>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
<mo stretchy="false">)</mo>
<msub>
<mi>g</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
<mo stretchy="false">)</mo>
<msub>
<mi>w</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{8}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}</annotation>
</semantics>
</math></span><img src="./eec15a77ec21a34b255e6fd4fd17829d88ddb3d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:22.34ex; height:7.343ex;" alt="{\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{8}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}" loading="lazy"></span>
</td>
<td>
</td>
<td colspan="3"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{7}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
<mo>=</mo>
<munderover>
<mo>∑<!-- ∑ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mn>7</mn>
</mrow>
</munderover>
<msub>
<mi>f</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">a</mi>
</mrow>
<mo stretchy="false">)</mo>
<msub>
<mi>g</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="bold">b</mi>
</mrow>
<mo stretchy="false">)</mo>
<msub>
<mi>w</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>i</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{7}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}</annotation>
</semantics>
</math></span><img src="./770d3d4fab36bbf9920a6c24544da02ae2b262d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:22.34ex; height:7.343ex;" alt="{\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{7}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}" loading="lazy"></span>
</td></tr></tbody></table>
<p>It can be shown that the total number of elementary multiplications <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>L</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle L}</annotation>
</semantics>
</math></span><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"></span> required for matrix multiplication is tightly asymptotically bound to the rank <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>R</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R}</annotation>
</semantics>
</math></span><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span>, i.e. <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L=\Theta (R)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>L</mi>
<mo>=</mo>
<mi mathvariant="normal">Θ<!-- Θ --></mi>
<mo stretchy="false">(</mo>
<mi>R</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle L=\Theta (R)}</annotation>
</semantics>
</math></span><img src="./b10f3949e296c673b22ec0d445c7822591a0121f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.063ex; height:2.843ex;" alt="{\displaystyle L=\Theta (R)}" loading="lazy"></span>, or more specifically, since the constants are known, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R/2\leq L\leq R}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>R</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mn>2</mn>
<mo>≤<!-- ≤ --></mo>
<mi>L</mi>
<mo>≤<!-- ≤ --></mo>
<mi>R</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle R/2\leq L\leq R}</annotation>
</semantics>
</math></span><img src="./86e4f0bf49fa49b04fd2bf682b54bf5457d0d385.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.633ex; height:2.843ex;" alt="{\displaystyle R/2\leq L\leq R}" loading="lazy"></span>. One useful property of the rank is that it is submultiplicative for <a href="Tensor_product" title="Tensor product">tensor products</a>, and this enables one to show that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}\times 2^{n}\times 2^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
<mo>×<!-- × --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
<mo>×<!-- × --></mo>
<msup>
<mn>2</mn>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2^{n}\times 2^{n}\times 2^{n}}</annotation>
</semantics>
</math></span><img src="./4c3f03c42253fd971d3e1719a90de59a37a6dd82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.824ex; height:2.343ex;" alt="{\displaystyle 2^{n}\times 2^{n}\times 2^{n}}" loading="lazy"></span> matrix multiplication can be accomplished with no more than <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 7n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>7</mn>
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 7n}</annotation>
</semantics>
</math></span><img src="./478f53cc7923e557d96c8dc5abafba06c0367c80.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.557ex; height:2.176ex;" alt="{\displaystyle 7n}" loading="lazy"></span> elementary multiplications for any <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>. (This <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>-fold tensor product of the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\times 2\times 2}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>2</mn>
<mo>×<!-- × --></mo>
<mn>2</mn>
<mo>×<!-- × --></mo>
<mn>2</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2\times 2\times 2}</annotation>
</semantics>
</math></span><img src="./128c392aacbd66d7eebc7f18ddd6256ca69e327f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.168ex; height:2.176ex;" alt="{\displaystyle 2\times 2\times 2}" loading="lazy"></span> matrix multiplication map with itself — an <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>-th tensor power—is realized by the recursive step in the algorithm shown.)
</p>
<div class="mw-heading mw-heading3"><h3 id="Cache_behavior">Cache behavior</h3></div>
<p>Strassen's algorithm is <a href="Cache-oblivious_algorithm" title="Cache-oblivious algorithm">cache oblivious</a>. Analysis of its <a href="CPU_cache" title="CPU cache">cache</a> behavior algorithm has shown it to incur
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta \left(1+{\frac {n^{2}}{b}}+{\frac {n^{\log _{2}7}}{b{\sqrt {M}}}}\right)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi mathvariant="normal">Θ<!-- Θ --></mi>
<mrow>
<mo>(</mo>
<mrow>
<mn>1</mn>
<mo>+</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
<mi>b</mi>
</mfrac>
</mrow>
<mo>+</mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>log</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⁡<!-- ⁡ --></mo>
<mn>7</mn>
</mrow>
</msup>
<mrow>
<mi>b</mi>
<mrow class="MJX-TeXAtom-ORD">
<msqrt>
<mi>M</mi>
</msqrt>
</mrow>
</mrow>
</mfrac>
</mrow>
</mrow>
<mo>)</mo>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \Theta \left(1+{\frac {n^{2}}{b}}+{\frac {n^{\log _{2}7}}{b{\sqrt {M}}}}\right)}</annotation>
</semantics>
</math></span><img src="./facfaccfc23932af8bbf33a69998239a0a111285.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:22.35ex; height:6.676ex;" alt="{\displaystyle \Theta \left(1+{\frac {n^{2}}{b}}+{\frac {n^{\log _{2}7}}{b{\sqrt {M}}}}\right)}" loading="lazy"></span></dd></dl>
<p>cache misses during its execution, assuming an idealized cache of size <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>M</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle M}</annotation>
</semantics>
</math></span><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"></span> (i.e. with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M/b}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mi>b</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle M/b}</annotation>
</semantics>
</math></span><img src="./7fc4a63bc63a3fcd0781a5eaedb4b3c28f95a3e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.602ex; height:2.843ex;" alt="{\displaystyle M/b}" loading="lazy"></span> lines of length <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>b</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle b}</annotation>
</semantics>
</math></span><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span>).<sup id="cite_ref-prokop_11-0" class="reference"><a href="#cite_note-prokop-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 13">: 13 </span></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="Implementation_considerations">Implementation considerations</h2></div>
<style data-mw-deduplicate="TemplateStyles:r1251242444">
/* start https://en.wikipedia.org/ */


.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}


/* end https://en.wikipedia.org/ */
</style>
<p>The description above states that the matrices are square, and the size is a power of two, and that padding should be used if needed. This restriction allows the matrices to be split in half, recursively, until limit of scalar multiplication is reached. The restriction simplifies the explanation, and analysis of complexity, but is not actually necessary;<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>
and in fact, padding the matrix as described will increase the computation time and can easily eliminate the fairly narrow time savings obtained by using the method in the first place.
</p><p>A good implementation will observe the following:
</p>
<ul><li>It is not necessary or desirable to use the Strassen algorithm down to the limit of scalars. Compared to conventional matrix multiplication, the algorithm adds a considerable <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>
</semantics>
</math></span><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy"></span> workload in addition/subtractions; so below a certain size, it will be better to use conventional multiplication. Thus, for instance, a <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1600\times 1600}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>1600</mn>
<mo>×<!-- × --></mo>
<mn>1600</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 1600\times 1600}</annotation>
</semantics>
</math></span><img src="./afc08cd512955c8dd15b56fcfca6a6ca52c4e211.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.14ex; height:2.176ex;" alt="{\displaystyle 1600\times 1600}" loading="lazy"></span> does not need to be padded to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2048\times 2048}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>2048</mn>
<mo>×<!-- × --></mo>
<mn>2048</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 2048\times 2048}</annotation>
</semantics>
</math></span><img src="./603e630df6e0b2be2085ebcb8a202e728b021cb0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.14ex; height:2.176ex;" alt="{\displaystyle 2048\times 2048}" loading="lazy"></span>, since it could be subdivided down to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 25\times 25}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>25</mn>
<mo>×<!-- × --></mo>
<mn>25</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 25\times 25}</annotation>
</semantics>
</math></span><img src="./dc2ddd4e4e0b1839c5af34a00280a2ed568b429a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.49ex; height:2.176ex;" alt="{\displaystyle 25\times 25}" loading="lazy"></span> matrices and conventional multiplication can then be used at that level.</li>
<li>The method can indeed be applied to square matrices of any dimension.<sup id="cite_ref-dalberto_3-1" class="reference"><a href="#cite_note-dalberto-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> If the dimension is even, they are split in half as described. If the dimension is odd, zero padding by one row and one column is applied first. Such padding can be applied on-the-fly and lazily, and the extra rows and columns discarded as the result is formed. For instance, suppose the matrices are <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 199\times 199}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>199</mn>
<mo>×<!-- × --></mo>
<mn>199</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 199\times 199}</annotation>
</semantics>
</math></span><img src="./ad07f0b7d604fab988242ef56317a990d4a25f5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.815ex; height:2.176ex;" alt="{\displaystyle 199\times 199}" loading="lazy"></span>. They can be split so that the upper-left portion is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 100\times 100}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>100</mn>
<mo>×<!-- × --></mo>
<mn>100</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 100\times 100}</annotation>
</semantics>
</math></span><img src="./b1448a349a70d30745936445235d9ce0bd2ca26d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.815ex; height:2.176ex;" alt="{\displaystyle 100\times 100}" loading="lazy"></span> and the lower-right is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 99\times 99}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>99</mn>
<mo>×<!-- × --></mo>
<mn>99</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 99\times 99}</annotation>
</semantics>
</math></span><img src="./cfe179ee592c01158aae916d87eef0dc0ea5ca1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.49ex; height:2.176ex;" alt="{\displaystyle 99\times 99}" loading="lazy"></span>. Wherever the operations require it, dimensions of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 99}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>99</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 99}</annotation>
</semantics>
</math></span><img src="./b1f4587c48bf9cc5cd6319a3b0655a07b6f611e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 99}" loading="lazy"></span> are zero padded to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 100}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>100</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 100}</annotation>
</semantics>
</math></span><img src="./0572cd017c6d7936a12737c9d614a2f801f94a36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 100}" loading="lazy"></span> first. Note, for instance, that the product <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M_{2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>M</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle M_{2}}</annotation>
</semantics>
</math></span><img src="./0d5d4dffae5ee0db4cc433e252ee9ed7530e5cf0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.308ex; height:2.509ex;" alt="{\displaystyle M_{2}}" loading="lazy"></span> is only used in the lower row of the output, so is only required to be <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 99}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>99</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 99}</annotation>
</semantics>
</math></span><img src="./b1f4587c48bf9cc5cd6319a3b0655a07b6f611e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 99}" loading="lazy"></span> rows high; and thus the left factor <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{21}+A_{22}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
<mo>+</mo>
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A_{21}+A_{22}}</annotation>
</semantics>
</math></span><img src="./4f4271c3d77ec66fcf0dd9a70e6a8c3b93b561ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.079ex; height:2.509ex;" alt="{\displaystyle A_{21}+A_{22}}" loading="lazy"></span> used to generate it need only be <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 99}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>99</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 99}</annotation>
</semantics>
</math></span><img src="./b1f4587c48bf9cc5cd6319a3b0655a07b6f611e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 99}" loading="lazy"></span> rows high; accordingly, there is no need to pad that sum to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 100}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>100</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 100}</annotation>
</semantics>
</math></span><img src="./0572cd017c6d7936a12737c9d614a2f801f94a36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 100}" loading="lazy"></span> rows; it is only necessary to pad <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{22}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>22</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A_{22}}</annotation>
</semantics>
</math></span><img src="./fcfa7914515f7c23e481f3f4602c8df3d791384a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.619ex; height:2.509ex;" alt="{\displaystyle A_{22}}" loading="lazy"></span> to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 100}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>100</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 100}</annotation>
</semantics>
</math></span><img src="./0572cd017c6d7936a12737c9d614a2f801f94a36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 100}" loading="lazy"></span> columns to match <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{21}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>A</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>21</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle A_{21}}</annotation>
</semantics>
</math></span><img src="./9e83e658fd24d00b7d28ae3e3ee88af82be7de9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.619ex; height:2.509ex;" alt="{\displaystyle A_{21}}" loading="lazy"></span>.</li></ul>
<p>Furthermore, there is no need for the matrices to be square. Non-square matrices can be split in half using the same methods, yielding smaller non-square matrices. If the matrices are sufficiently non-square it will be worthwhile reducing the initial operation to more square products, using simple methods which are essentially <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>
</semantics>
</math></span><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy"></span>, for instance:
</p>
<ul><li>A product of size <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [2N\times N]\ast [N\times 10N]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">[</mo>
<mn>2</mn>
<mi>N</mi>
<mo>×<!-- × --></mo>
<mi>N</mi>
<mo stretchy="false">]</mo>
<mo>∗<!-- ∗ --></mo>
<mo stretchy="false">[</mo>
<mi>N</mi>
<mo>×<!-- × --></mo>
<mn>10</mn>
<mi>N</mi>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle [2N\times N]\ast [N\times 10N]}</annotation>
</semantics>
</math></span><img src="./4584975c730400e1c1d3baa092b97f28e44cb068.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.205ex; height:2.843ex;" alt="{\displaystyle [2N\times N]\ast [N\times 10N]}" loading="lazy"></span> can be done as 20 separate <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [N\times N]\ast [N\times N]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">[</mo>
<mi>N</mi>
<mo>×<!-- × --></mo>
<mi>N</mi>
<mo stretchy="false">]</mo>
<mo>∗<!-- ∗ --></mo>
<mo stretchy="false">[</mo>
<mi>N</mi>
<mo>×<!-- × --></mo>
<mi>N</mi>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle [N\times N]\ast [N\times N]}</annotation>
</semantics>
</math></span><img src="./91127ead046d3d92db468b91863409f7056d490d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.717ex; height:2.843ex;" alt="{\displaystyle [N\times N]\ast [N\times N]}" loading="lazy"></span> operations, arranged to form the result;</li>
<li>A product of size <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [N\times 10N]\ast [10N\times N]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">[</mo>
<mi>N</mi>
<mo>×<!-- × --></mo>
<mn>10</mn>
<mi>N</mi>
<mo stretchy="false">]</mo>
<mo>∗<!-- ∗ --></mo>
<mo stretchy="false">[</mo>
<mn>10</mn>
<mi>N</mi>
<mo>×<!-- × --></mo>
<mi>N</mi>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle [N\times 10N]\ast [10N\times N]}</annotation>
</semantics>
</math></span><img src="./c48165aaaad10227c2ab2f8964bbbebe30eb2dfb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.367ex; height:2.843ex;" alt="{\displaystyle [N\times 10N]\ast [10N\times N]}" loading="lazy"></span> can be done as 10 separate <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [N\times N]\ast [N\times N]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">[</mo>
<mi>N</mi>
<mo>×<!-- × --></mo>
<mi>N</mi>
<mo stretchy="false">]</mo>
<mo>∗<!-- ∗ --></mo>
<mo stretchy="false">[</mo>
<mi>N</mi>
<mo>×<!-- × --></mo>
<mi>N</mi>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle [N\times N]\ast [N\times N]}</annotation>
</semantics>
</math></span><img src="./91127ead046d3d92db468b91863409f7056d490d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.717ex; height:2.843ex;" alt="{\displaystyle [N\times N]\ast [N\times N]}" loading="lazy"></span> operations, summed to form the result.</li></ul>
<p>These techniques will make the implementation more complicated, compared to simply padding to a power-of-two square; however, it is a reasonable assumption that anyone undertaking an implementation of Strassen, rather than conventional multiplication, will place a higher priority on computational efficiency than on simplicity of the implementation.
</p><p>In practice, Strassen's algorithm can be implemented to attain better performance than conventional multiplication even for matrices as small as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 500\times 500}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>500</mn>
<mo>×<!-- × --></mo>
<mn>500</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 500\times 500}</annotation>
</semantics>
</math></span><img src="./a8ebb1b72f8b8c100b2f6186343221d77636f4b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.815ex; height:2.176ex;" alt="{\displaystyle 500\times 500}" loading="lazy"></span>, for matrices that are not at all square, and without requiring workspace beyond buffers that are already needed for a high-performance conventional multiplication.<sup id="cite_ref-huang_et_al._4-1" class="reference"><a href="#cite_note-huang_et_al.-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2></div>
<ul><li><a href="Computational_complexity_of_mathematical_operations" title="Computational complexity of mathematical operations">Computational complexity of mathematical operations</a></li>
<li><a href="Gauss%E2%80%93Jordan_elimination" class="mw-redirect" title="Gauss–Jordan elimination">Gauss–Jordan elimination</a></li>
<li><a href="Computational_complexity_of_matrix_multiplication" title="Computational complexity of matrix multiplication">Computational complexity of matrix multiplication</a></li>
<li><a href="Z-order_curve" title="Z-order curve">Z-order curve</a></li>
<li><a href="Karatsuba_algorithm" title="Karatsuba algorithm">Karatsuba algorithm</a>, for multiplying <i>n</i>-digit integers in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{\log _{2}3})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<msub>
<mi>log</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>⁡<!-- ⁡ --></mo>
<mn>3</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O(n^{\log _{2}3})}</annotation>
</semantics>
</math></span><img src="./770c7081e94ce7027c145a2f892341605e9b0272.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.352ex; height:3.176ex;" alt="{\displaystyle O(n^{\log _{2}3})}" loading="lazy"></span> instead of in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>O</mi>
<mo stretchy="false">(</mo>
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation>
</semantics>
</math></span><img src="./6cd9594a16cb898b8f2a2dff9227a385ec183392.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" loading="lazy"></span> time
<ul><li>A similar <a href="Multiplication_algorithm#Complex_number_multiplication" title="Multiplication algorithm">complex multiplication algorithm</a> multiplies two complex numbers using 3 real multiplications instead of 4</li></ul></li>
<li><a href="Toom%E2%80%93Cook_multiplication" title="Toom–Cook multiplication">Toom-Cook algorithm</a>, a faster generalization of the Karatsuba algorithm that permits recursive divide-and-conquer decomposition into more than 2 blocks at a time</li></ul>
<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>
<style data-mw-deduplicate="TemplateStyles:r1239543626">
/* start https://en.wikipedia.org/ */


.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}


/* end https://en.wikipedia.org/ */
</style><div class="reflist">
<div class="mw-references-wrap mw-references-columns"><ol class="references">
<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">
/* start https://en.wikipedia.org/ */


.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}


/* end https://en.wikipedia.org/ */
</style><cite id="CITEREFStrassen1969" class="citation journal cs1">Strassen, Volker (1969). "Gaussian Elimination is not Optimal". <i>Numer. Math</i>. <b>13</b> (4): <span class="nowrap">354–</span>356. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02165411">10.1007/BF02165411</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a>&nbsp;<a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:121656251">121656251</a>.</cite></span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFSkiena1998" class="citation cs2">Skiena, Steven S. (1998), "§8.2.3 Matrix multiplication", <i>The Algorithm Design Manual</i>, Berlin, New York: <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a>&nbsp;<bdi>978-0-387-94860-7</bdi></cite>.</span>
</li>
<li id="cite_note-dalberto-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-dalberto_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-dalberto_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFD'AlbertoNicolau2005" class="citation conference cs1">D'Alberto, Paolo; Nicolau, Alexandru (2005). <a rel="nofollow" class="external text" href="https://www.ics.uci.edu/~paolo/Reference/paoloA.ishp-vi.pdf"><i>Using Recursion to Boost ATLAS's Performance</i></a> <span class="cs1-format">(PDF)</span>. Sixth Int'l Symp. on High Performance Computing.</cite></span>
</li>
<li id="cite_note-huang_et_al.-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-huang_et_al._4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-huang_et_al._4-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFHuangSmithHenryvan_de_Geijn2016" class="citation conference cs1">Huang, Jianyu; Smith, Tyler M.; Henry, Greg M.; van de Geijn, Robert A. (13 Nov 2016). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/315365781"><i>Strassen's Algorithm Reloaded</i></a>. <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/xpl/conhome/7875333/proceeding">SC16: The International Conference for High Performance Computing, Networking, Storage and Analysis</a>. IEEE Press. pp.&nbsp;<span class="nowrap">690–</span>701. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSC.2016.58">10.1109/SC.2016.58</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a>&nbsp;<bdi>9781467388153</bdi><span class="reference-accessdate">. Retrieved <span class="nowrap">1 Nov</span> 2022</span>.</cite></span>
</li>
<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFWinograd1971" class="citation journal cs1">Winograd, S. (October 1971). <a rel="nofollow" class="external text" href="https://linkinghub.elsevier.com/retrieve/pii/0024379571900097">"On multiplication of 2 × 2 matrices"</a>. <i>Linear Algebra and Its Applications</i>. <b>4</b> (4): <span class="nowrap">381–</span>388. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0024-3795%2871%2990009-7">10.1016/0024-3795(71)90009-7</a>.</cite></span>
</li>
<li id="cite_note-FOOTNOTEKnuth1997500-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEKnuth1997500_6-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFKnuth1997">Knuth (1997)</a>, p.&nbsp;500.</span>
</li>
<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFKarstadtSchwartz2017" class="citation book cs1">Karstadt, Elaye; Schwartz, Oded (2017-07-24). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/3087556.3087579">"Matrix Multiplication, a Little Faster"</a>. <i>Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures</i>. ACM. pp.&nbsp;<span class="nowrap">101–</span>110. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3087556.3087579">10.1145/3087556.3087579</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a>&nbsp;<bdi>978-1-4503-4593-4</bdi>.</cite></span>
</li>
<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFSchwartzVaknin2023" class="citation journal cs1">Schwartz, Oded; Vaknin, Noa (2023-12-31). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://epubs.siam.org/doi/10.1137/22M1502719">"Pebbling Game and Alternative Basis for High Performance Matrix Multiplication"</a></span>. <i>SIAM Journal on Scientific Computing</i>. <b>45</b> (6): <span class="nowrap">C277 –</span> <span class="nowrap">C303</span>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2023SJSC...45C.277S">2023SJSC...45C.277S</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F22M1502719">10.1137/22M1502719</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a>&nbsp;<a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1064-8275">1064-8275</a>.</cite></span>
</li>
<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFWebb1975" class="citation journal cs1">Webb, Miller (1975). "Computational complexity and numerical stability". <i>SIAM J. Comput</i>. <b>4</b> (2): <span class="nowrap">97–</span>107. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0204009">10.1137/0204009</a>.</cite></span>
</li>
<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFBurgisserClausenShokrollahi1997" class="citation book cs1">Burgisser; Clausen; Shokrollahi (1997). <i>Algebraic Complexity Theory</i>. Springer-Verlag. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a>&nbsp;<bdi>3-540-60582-7</bdi>.</cite></span>
</li>
<li id="cite_note-prokop-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-prokop_11-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFFrigoLeisersonProkopRamachandran1999" class="citation conference cs1">Frigo, M.; <a href="Charles_Leiserson" class="mw-redirect" title="Charles Leiserson">Leiserson, C. E.</a>; <a href="Harald_Prokop" title="Harald Prokop">Prokop, H.</a>; Ramachandran, S. (1999). <a rel="nofollow" class="external text" href="http://supertech.csail.mit.edu/papers/FrigoLePr99.pdf"><i>Cache-oblivious algorithms</i></a> <span class="cs1-format">(PDF)</span>. Proc. IEEE Symp. on Foundations of Computer Science (FOCS). pp.&nbsp;<span class="nowrap">285–</span>297.</cite></span>
</li>
<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><cite id="CITEREFHigham1990" class="citation journal cs1">Higham, Nicholas J. (1990). <a rel="nofollow" class="external text" href="http://www.maths.manchester.ac.uk/~higham/papers/high90s.pdf">"Exploiting fast matrix multiplication within the level 3 BLAS"</a> <span class="cs1-format">(PDF)</span>. <i>ACM Transactions on Mathematical Software</i>. <b>16</b> (4): <span class="nowrap">352–</span>368. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F98267.98290">10.1145/98267.98290</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/1813%2F6900">1813/6900</a></span>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a>&nbsp;<a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5715053">5715053</a>.</cite></span>
</li>
</ol></div></div>
<ul><li><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Thomas H. Cormen</a>, <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, <a href="Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Ronald L. Rivest</a>, and <a href="Clifford_Stein" title="Clifford Stein">Clifford Stein</a>. <i><a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a></i>, Second Edition. MIT Press and McGraw-Hill, 2001. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a>&nbsp;<bdi>0-262-03293-7</bdi>. Chapter 28: Section 28.2: Strassen's algorithm for matrix multiplication, pp.&nbsp;735–741.</li>
<li><cite id="CITEREFKnuth1997" class="citation book cs1">Knuth, Donald (1997). <i>The Art of Computer Programming, Seminumerical Algorithms</i>. Vol.&nbsp;II (3rd&nbsp;ed.). Addison-Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a>&nbsp;<bdi>0-201-89684-2</bdi>.</cite></li></ul>
<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>
<ul><li><span class="citation mathworld" id="Reference-Mathworld-Strassen's_Formulas"><cite id="CITEREFWeisstein" class="citation web cs1"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/StrassenFormulas.html">"Strassen's Formulas"</a>. <i><a href="MathWorld" title="MathWorld">MathWorld</a></i>.</cite></span> (also includes formulas for fast <a href="Matrix_inversion" class="mw-redirect" title="Matrix inversion">matrix inversion</a>)</li>
<li>Tyler J. Earnest, <i><a rel="nofollow" class="external text" href="https://web.archive.org/web/20100612150812/http://www.mc2.umbc.edu/docs/earnest.pdf">Strassen's Algorithm on the Cell Broadband Engine</a></i></li></ul>
<div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">
/* start https://en.wikipedia.org/ */


.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}


/* end https://en.wikipedia.org/ */
</style><style data-mw-deduplicate="TemplateStyles:r1236075235">
/* start https://en.wikipedia.org/ */


.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}


/* end https://en.wikipedia.org/ */
</style></div><div role="navigation" class="navbox" aria-labelledby="Numerical_linear_algebra64" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">
/* start https://en.wikipedia.org/ */


.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}


/* end https://en.wikipedia.org/ */
</style><div id="Numerical_linear_algebra64" style="font-size:114%;margin:0 4em"><a href="Numerical_linear_algebra" title="Numerical linear algebra">Numerical linear algebra</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Key concepts</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Floating_point" class="mw-redirect" title="Floating point">Floating point</a></li>
<li><a href="Numerical_stability" title="Numerical stability">Numerical stability</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Problems</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="System_of_linear_equations" title="System of linear equations">System of linear equations</a></li>
<li><a href="Matrix_decomposition" title="Matrix decomposition">Matrix decompositions</a></li>
<li><a href="Matrix_multiplication" title="Matrix multiplication">Matrix multiplication</a> (<a href="Matrix_multiplication_algorithm" title="Matrix multiplication algorithm">algorithms</a>)</li>
<li><a href="Matrix_splitting" title="Matrix splitting">Matrix splitting</a></li>
<li><a href="Sparse_matrix" title="Sparse matrix">Sparse problems</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Hardware</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="CPU_cache" title="CPU cache">CPU cache</a></li>
<li><a href="Translation_lookaside_buffer" title="Translation lookaside buffer">TLB</a></li>
<li><a href="Cache-oblivious_algorithm" title="Cache-oblivious algorithm">Cache-oblivious algorithm</a></li>
<li><a href="Single_instruction%2C_multiple_data" title="Single instruction, multiple data">SIMD</a></li>
<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li></ul>
</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Software</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">
<ul><li><a href="Automatically_Tuned_Linear_Algebra_Software" title="Automatically Tuned Linear Algebra Software">ATLAS</a></li>
<li><a href="MATLAB" title="MATLAB">MATLAB</a></li>
<li><a href="Basic_Linear_Algebra_Subprograms" title="Basic Linear Algebra Subprograms">Basic Linear Algebra Subprograms (BLAS)</a></li>
<li><a href="LAPACK" title="LAPACK">LAPACK</a></li>
<li><a href="Comparison_of_linear_algebra_libraries" title="Comparison of linear algebra libraries">Specialized libraries</a></li>
<li><a href="Comparison_of_numerical-analysis_software" title="Comparison of numerical-analysis software">General purpose software</a></li></ul>
</div></td></tr></tbody></table></div></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2025-07-10" href="https://en.wikipedia.org/wiki/?title=Strassen_algorithm&amp;oldid=1299749964">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>

</body></html>